package com.lihepeng.leecode.classic.kmp;

import org.junit.Test;

/**
 * KMP  算法
 * 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，
 * 我想知道，里面是否包含另一个字符串"ABCDABD"？
 * 模糊匹配
 */

public class StrSearch1 {
    public static int[] getNext(String ps) {
        char[] chars = ps.toCharArray();
        int[] next = new int[chars.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < chars.length - 1) {
            if (k == -1 || chars[j] == chars[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }

        }
        return next;
    }

    @Test
    public void runTest() {

        String s = "s1111";
        boolean s1 = s.contains("s");
        System.out.println(s1);
    }

}
